// 53.最大子数组和
package LeetcodeHot100;

public class Solution053 {
    public int maxSubArray(int[] nums) {
        // 定义
        int[] dp = new int[nums.length]; // dp[i]表示以nums[i]结尾的最大子数组和
        // 初始化
        dp[0] = nums[0];
        int result = dp[0];
        // 状态转移
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(0, dp[i - 1]) + nums[i];
            if (dp[i] > result)
                result = dp[i];
        }
        return result;
    }
}
